package cn.edu.xjtu.carlWay.stackAndQueue.evalRPN;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 150. 逆波兰表达式求值
 * 根据 逆波兰表示法，求表达式的值。
 * <p>
 * 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
 * <p>
 * 注意 两个整数之间的除法只保留整数部分。
 * <p>
 * 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        String[] tokens = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
        System.out.println(evalRPN(tokens));
    }

    public static int evalRPN(String[] tokens) {
        Deque<Integer> num_stack = new LinkedList<>();

        for (String str : tokens) {
            if (str.matches("-?\\d+")) {
                num_stack.addFirst(Integer.parseInt(str));
            } else {
                int res = 0;
                int firstNum = num_stack.removeFirst();
                int secondNum = num_stack.removeFirst();
                switch (str) {
                    case "+":
                        res = firstNum + secondNum;
                        break;
                    case "-":
                        res = secondNum - firstNum;
                        break;
                    case "*":
                        res = firstNum * secondNum;
                        break;
                    case "/":
                        res = secondNum / firstNum;
                        break;
                }
                num_stack.addFirst(res);
            }
        }
        return num_stack.pop();
    }
}


